/*************************************************************************
	> File Name: 002.heap_sort.c
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 二  9/21 18:43:50 2021
 ************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define swap(a, b) {\
    __typeof(a) __temp = a;\
    a = b; \
    b = __temp; \
}

//写法一：线性建堆法，自上向下调整堆（下滤）
void percolateDown(int *arr, int n, int ind) {
    while ((ind << 1) <= n) {
        int temp = ind, left = ind << 1, right = ind << 1 | 1;
        if (arr[left] > arr[temp]) temp = left;
        if (right <= n && arr[right] > arr[temp]) temp = right;
        if (temp == ind) break;
        swap(arr[temp], arr[ind]);
        ind = temp;
    }
}

//写法二：自上而下调整堆（下滤）
void percolateDown2(int *arr, int n, int ind) {
    int tmp = arr[ind];
    int child;
    while ((ind << 1) <= n) {
        child = ind << 1;
        if (child != n && arr[child + 1] > arr[child]) { //找到两个孩子节点中值大的
            child++;
        }
        if (tmp < arr[child]) {
            arr[ind] = arr[child];
            ind = child;
        } else {
            break;
        }
    }
    //确定了tmp值应该放置的位置
    arr[ind] = tmp;
    return ;
}

//堆排序
void heap_sort(int *arr, int n) {
    //通过arr[1]获取整个数组的值,此处的arr修改并不会影响实参arr
    arr -= 1; 
    //从倒数第二层开始往下调整
    for (int i = n >> 1; i >= 1; i--) {
        //percolateDown(arr, n, i);
        percolateDown2(arr, n, i);
    }

    //头部弹出调整，得到排序从小到大的结果
    for (int i = n; i > 1; i--) {
        swap(arr[i], arr[1]);
        //percolateDown(arr, i - 1, 1);
        percolateDown2(arr, i - 1, 1);
    }

    return ;
}

void output(int *arr, int n) {
    printf("[");
    for (int i = 0; i < n; i++) {
        printf(" %d", arr[i]);
    }
    printf("]\n");
    return ;
}


int main() {
    srand(time(0)); //初始化随机种子
    #define max_n 20 
    int *arr = (int *)malloc(sizeof(int) * max_n);
    for (int i = 0; i < max_n; i++) {
        arr[i] = rand() % 100;
    }
    output(arr, max_n);
    heap_sort(arr, max_n);
    output(arr, max_n);
    free(arr);
    #undef max_n

    return 0;
}
